#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣198. 打家劫舍
// 【难度】中等
// 【提交】2025.10.21 https://leetcode.cn/problems/house-robber/submissions/672449056/
// 【标签】动态规划
class Solution_LC0198 {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size() + 1, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < nums.size() + 1; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.size()];
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums，表示每个房屋存放的金额。如果两间相邻的房屋在同一晚上被偷，系统会自动报警。
 * 计算在不触动警报装置的情况下，能够偷窃到的最高金额。
 * 模型：动态规划，通过状态转移计算最大收益。
 * 
 * 二、标准解法状态设计
 * 设dp[i]表示前i个房屋能偷窃到的最高金额。
 * 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
 * 初始状态：dp[0] = 0, dp[1] = nums[0]
 * 
 * 三、你的实现思路
 * 使用动态规划方法，通过dp数组记录前i个房屋的最大收益。
 * 对于每个房屋，选择偷或不偷，取两者中的最大值。
 * 
 * 四、复杂度
 * 时间：O(n)，需要遍历一次数组。
 * 空间：O(n)，需要dp数组存储中间结果。
 * 
 * 五、优缺点分析
 * 优点：
 *   - 算法思路清晰，易于理解；
 *   - 时间复杂度低，能够处理较大规模数据。
 * 缺点：
 *   - 空间复杂度可以进一步优化；
 *   - 对于边界情况需要特殊处理。
 * 
 * 六、改进建议
 * 1. 可以优化空间复杂度到O(1)，只保存前两个状态；
 * 2. 可以添加输入验证：if (nums.empty()) return 0;
 * 3. 对于只有一个房屋的情况可以直接返回。
 * 
 * 七、一句话总结
 * 动态规划是解决打家劫舍问题的标准方法，你的实现准确且高效。
 */